//
// Created by acer on 2018/4/25.
//
#include <stdio.h>
#define tmp(x, y) ((x) < (y))
#define length 10000
extern void print_array(int array[]);
extern void swap (int *a, int *b)
{
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

//插入排序: [已经排好序] <-（取出元素按序插入）  [未排好序的]
void insertion_sort(int *array)
{
    int i, j, temp;
    printf("array is \n");
    //print_array(array);
    printf("start sorting...\n");
    for(i = 1; i < length; i++)
    {
        if(array[i] < array[i-1]) {
//            temp = array[i];
//            for (j = i - 1; (j >= 0) && (array[j] > temp); j--) {
//                array[j + 1] = array[j];
//            }
//            array[j + 1] = temp;

            for (j = i; (array[j] < array[j-1]) && (j > 0); --j) {
                swap(&array[j], &array[j - 1]);
            }
            //printf("N0.%d   ", i);
            //print_array(array);
        }
    }
}

//插入排序(折半查找): [已经排好序] <-（取出元素按序插入）  [未排好序的]
void select_sort_Halved_find(int *array){
    int i, j, temp;
    printf("array is \n");
    //print_array(array);
    printf("start sorting...\n");
    for(i = 1; i < length; i++)
    {
        if(array[i] < array[i-1]) {
            int leftPoint = 0;
            int rightPint = i-1;
            int target = array[i];
            //折半查找
            while (leftPoint < rightPint){
                int mid = (leftPoint + rightPint) / 2;
                if (array[mid] > target){
                    rightPint = mid - 1;
                }
                else{
                 leftPoint = mid + 1;
                }
            }
            for (j = i; (array[j] < array[j-1]) && (j > rightPint); --j) {
                swap(&array[j], &array[j - 1]);
            }

        }
    }
}


//冒泡排序: [已经排好序] <-（取出最小/最大元素按插入最后一个）  [未排好序的]
void popupSort(int *array){
    printf("array is \n");
    print_array(array);
    for(int i = 0; i < length; i++){
        for (int j = length - 1; j > i; j--) {
            if(array[j] < array[j-1]){
                swap(&array[j], &array[j-1]);
            }
        }
        print_array(array);
    }
}

//选择排序: [已经排好序] <-（取出最小/最大元素按插入最后一个）  [未排好序的]
void selectSort(int *array){
    for (int i = 0; i < length; ++i) {
        int min = array[i];
        int minInd = i;
        for (int j = i + 1; j < length ; ++j) {
            if(array[j] < min){
                min = array[j];
                minInd = j;
            }
        }
        array[minInd] = array[i];
        array[i] = min;

        print_array(array);
    }
}

//希尔排序
void ShellSort(int *array){
    int increment, i, j, tmp;
    for (increment = length/2; increment > 0 ; increment/= 2) {
        for(i = increment; i < length; i++){
            tmp = array[i];
            for(j = i - increment; j >= 0 && tmp < array[j]; j -= increment){
                array[j + increment] = array[j];
            }
            array[j + increment] = tmp;
        }
    }
}

//快排
void quickSort(int *array, int low, int high){
    int tmp;
    int i = low, j = high;
    if(low < high){
        tmp = array[low];
        while(i < j){
            while (j > i && array[j] > tmp){
                j -= 1;
            }
            if(i < j){
                array[i] = array[j];
                i += 1;
            }
            while(i < j && array[i] < tmp){
                i += 1;
            }
            if(i < j){
                array[j] = array[i];
                j -= 1;
            }
        }
        array[i] = tmp;
        quickSort(array, low, i-1);
        quickSort(array, i+1, high);
    } else{
        return;
    }
}


















